﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>

#include<cstdlib>
#include<cassert>
using namespace std;

template<class k,class v>
struct node {
	node<k, v>* _parent;
	node<k, v>* _left;
	node<k, v>* _right;
	pair<k, v> _p;
	int _bf;

	node(const pair<k, v>& p)
		:_parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
		, _p(p)
		, _bf(0) {
	}
};

template<class k,class v>
class avl {
	typedef node<k,v> node;
public:
	bool Insert(pair<k,v> a) {
		if (!_root) {
			_root = new node(a);
			return true;
		}

		node* parent = _root;
		node* cur = _root;
		while (cur) {
			if (cur->_p.first < a.first) {
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_p.first > a.first) {
				parent = cur;
				cur = cur->_left;
			}
			else {
				return false;
			}
		}

		node* add = new node(a);
		if (parent->_p.first<a.first) {
			parent->_right = add;
		}
		else {
			parent->_left = add;
		}
		add->_parent = parent;

		cur = add;
		while (parent) {//注意循环逻辑
			if (parent->_right == cur) {
				++parent->_bf;
			}
			else
				--parent->_bf;

			if ( parent->_bf == 0)
				break;
			else if (abs(parent->_bf) == 1) {
				cur = parent;
				parent = parent->_parent;
			}
			else if (abs(parent->_bf) == 2) {
				if (parent->_bf == -2) {
					if (parent->_bf == -2 && parent->_left->_bf == -1) {
						RightRotation(parent);
					}
					else if (parent->_left && parent->_left->_bf == 1) {
						LRRotation(parent);
					}
				}
				else if (parent->_bf == 2) {
					if (parent->_right && parent->_right->_bf == 1) {
						LeftRotation(parent);
					}

					else if (parent->_right && parent->_right->_bf == -1) {
						RLRotation(parent);
					}
				}
				else {
					assert(false);
				}

				break;
			}
			else
			assert(false);
		}

		return true;
	}

	node* Find(const k& key) {
		if (!_root) {
			return nullptr;
		}

		node* cur = _root;
		while (cur) {
			if (cur->_p.first < key) {
				cur = cur->_left;
			}
			else if (cur->_p.first > key) {
				cur = cur->_right;
			}
			else {
				return cur;
			}
		}

		return nullptr;
	}

	int Height() {
		return height(_root);
	}
	int height(node* n) {
		if (!n) {
			return 0;
		}

		int LeftHeight = height(n->_left);
		int RightHeight = height(n->_right);

		return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
	}

	bool IsBalanced() {
		return Is_Balanced(_root);
	}
	bool Is_Balanced(node* n) {
		if (!n) {
			return true;
		}

		int LH = height(n->_left);
		int RH = height(n->_right);
		int diff = RH - LH;

		if ( diff!= n->_bf|| abs(n->_bf)>1) {
			if (diff != n->_bf) {
				cout << n->_p.first << "处高度差不等于平衡因子" << endl;

			}
			if (abs(n->_bf) > 1) {
				cout << n->_p.first << "处平衡因子大于1" << endl;
			}

			return false;
		}
		
		return Is_Balanced(n->_left) && Is_Balanced(n->_right);
	}

	int Size() {
		return size(_root);
	}
	int size(node* n) {
		if (!n) {
			return 0;
		}

		int ln = size(n->_left);
		int rn = size(n->_right);

		return ln + rn + 1;
	}

	void Inorder() {
		InOrder(_root);
	}
	void InOrder(node* n) {
		if (!n) {
			return;
		}

		InOrder(n->_left);
		cout << n->_p.first << ":" << n->_bf << endl;
		InOrder(n->_right);
	}

	void RightRotation(node* parent) {
		node* SL = parent->_left;
		node* SLR = SL->_right;

		parent->_left = SLR;
		if (SLR) {//注意细节
			SLR->_parent = parent;
		}

		SL->_parent = parent->_parent;
		if (parent->_parent) {
			if (parent->_parent->_left == parent) {
				parent->_parent->_left = SL;
			}
			else {
				parent->_parent->_right = SL;
			}
		}
		else {
			_root = SL;//注意细节
		}

		SL->_right = parent;
		parent->_parent = SL;

		parent->_bf = SL->_bf = 0;
	}
	void LeftRotation(node* parent) {
		node* SR = parent->_right;
		node* SRL = SR->_left;

		parent->_right = SRL;
		if (SRL) {
			SRL->_parent = parent;
		}

		SR->_parent = parent->_parent;
		if (parent->_parent) {
			if (parent->_parent->_left == parent) {
				parent->_parent->_left = SR;
			}
			else {
				parent->_parent->_right = SR;
			}
		}
		else {
			_root = SR;
		}

		SR->_left = parent;
		parent->_parent = SR;

		parent->_bf = SR->_bf = 0;
	}
	void LRRotation(node* parent) {
		node* SL = parent->_left;
		node* SLR = SL->_right;
		int bf = SLR->_bf;

		LeftRotation(parent->_left);
		RightRotation(parent);

		if (bf == 0) {
			SL->_bf = SLR->_bf = parent->_bf = 0;
		}
		else if (bf == 1) {
			SLR->_bf = parent->_bf = 0;
			SL->_bf = -1;
		}
		else if (bf == -1) {
			SL->_bf = SLR->_bf = 0;
			parent->_bf = 1;
		}
		else {
			assert(false);
		}
	}
	void RLRotation(node* parent) {
		node* SR = parent->_right;
		node* SRL = SR->_left;
		int bf = SRL->_bf;

		RightRotation(parent->_right);
		LeftRotation(parent);

		if (bf == 0) {
			SR->_bf = SRL->_bf = parent->_bf = 0;
		}
		else if (bf == 1) {
			SRL->_bf = SR->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1) {
			parent->_bf = SRL->_bf = 0;
			SR->_bf = 1;
		}
		else {
			assert(false);
		}
	}

private:
	node* _root = nullptr;
};

void test1() {
	class avl<int, int> av;
	// 常规的测试⽤例 
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	// 特殊的带有双旋场景的测试⽤例 
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };

	for (auto e : a) {
		av.Insert({ e, e });
	}
	cout << av.IsBalanced() << endl;
	cout << "Height:" << av.Height() << endl;
	av.Inorder();

	int b = 0;

}
void test2() {
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
	size_t begin2 = clock();
	avl<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << "Insert:" << end2 - begin2 << endl;
	cout << t.IsBalanced() << endl;
	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;
	size_t begin1 = clock();
	// 确定在的值 
	/*for (auto e : v)
	{
	t.Find(e);
	}*/
	// 随机值 
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << endl;
}

int main() {
	test2();
	return 0;
}